package com.sunny;

import java.util.Scanner;

public class Main {

    private static final Scanner SCANNER = new Scanner(System.in);

    public static void main(String[] args) {

        /*1 2 5 8 0 0 9 0 0 0 3 6 0 7 0 0 0*/
        Node root = createTreePre();

        preOrder(root);
        System.out.println();

        System.out.println("**************************");

        inOrder(root);
        System.out.println();

        System.out.println("**************************");

        postOrder(root);
        System.out.println();

        System.out.println("**************************");

        layerOrder(root);

    }

    public static Node createTreePre(){

        int val = SCANNER.nextInt();
        Node node = null;
        if(0 == val){
            return node;
        }
        node = new Node(val);
        node.setLeft(createTreePre());
        node.setRight(createTreePre());
        return node;

    }

    public static void preOrder(Node node){

        if(null == node)
            return;

        System.out.print(node.getValue() + " ");
        preOrder(node.getLeft());
        preOrder(node.getRight());

    }

    public static void inOrder(Node node){

        if(null == node)
            return;

        inOrder(node.getLeft());
        System.out.print(node.getValue() + " ");
        inOrder(node.getRight());

    }

    public static void postOrder(Node node){

        if(null == node)
            return;

        postOrder(node.getLeft());
        postOrder(node.getRight());
        System.out.print(node.getValue() + " ");

    }

    public static void layerOrder(Node root) {
        int deepLength = deep(root);
        for (int i = 1; i <= deepLength; i++) {
            layerOrder(root, i);
        }
    }

    private static int deep(Node node) {
        int res = 0;
        if (node == null) {
            return res;
        }
        res = Math.max(res, deep(node.getLeft()) + 1);
        res = Math.max(res, deep(node.getRight()) + 1);
        return res;
    }

    public static void layerOrder(Node node, int level) {
        if (node == null || level == 0) {
            return ;
        }
        if (level == 1) {
            System.out.print(node.getValue() + " ");
        }
        layerOrder(node.left, level - 1);
        layerOrder(node.right, level - 1);
    }

}

class Node{

    int value;
    Node left,right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}